package com.example.tree.bst;

import com.example.tree.TreeNode;

public class Leetcode1373_MaxSumBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(-4);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(-5);
        System.out.println(maxSumBST2(root));

    }

    /**
     * 解法二:优化解法
     *
     * BST = 左子树是BST + 右子树是BST + 左子树最大值< 根结点值+ 右子树最小值>= 根结点值
     *
     * 采用后序遍历的方式，左-> 右-> 根，所有节点只需遍历一次
     * 后序遍历能拿到左右子树遍历的状态结果
     * @param root
     * @return
     */
    public static int maxSumBST2(TreeNode root) {

        int[] max = new int[1];
        afterTraverse(root, max);
        return max[0];
    }

    /**
     * 后序遍历并更新状态()
     * @param root
     * @param max
     * @return
     */
    private static Result afterTraverse(TreeNode root, int[] max) {
        if (root == null) {
            return null;
        }

        Result leftRes = afterTraverse(root.left, max);
        Result rightRes = afterTraverse(root.right, max);

        // 主功能主要是完成下面的判断
        // BST = 左子树是BST + 右子树是BST + 左子树最大值< 根结点值+ 右子树最小值>= 根结点值
        if (leftRes != null && (!leftRes.isBST || leftRes.max >= root.val)) {// 左子树不是二叉搜索树时
            return new Result(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, false);
        }
        if (rightRes != null && (!rightRes.isBST || rightRes.min <= root.val)) {// 右子树不是二叉搜索树时
            return new Result(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, false);
        }

        // 左右都是二叉搜索树时，此时需要更新状态
        // 1.更新键值和
        int nSum = leftRes == null ? 0 : leftRes.sum;
        nSum += rightRes == null ? 0 : rightRes.sum;
        nSum += root.val;

        // 2.更新最大/小值
        int minval = leftRes == null ? root.val : leftRes.min;
        int maxval = rightRes == null ? root.val : rightRes.max;
        max[0] = Math.max(max[0], nSum);
        return new Result(minval, maxval, nSum, true);
    }

    static class Result {
        int min; // 子树的最小值
        int max; // 子树的最大值
        int sum; // 子树键值和
        boolean isBST; // 是否是BST

        public Result(int min, int max, int sum, boolean isBST) {
            this.min = min;
            this.max = max;
            this.sum = sum;
            this.isBST = isBST;
        }
    }




    /**
     * 解法一:暴力法
     *
     * 先序递归遍历每个子树
     * 判断该子树是否是二叉搜索树，
     *   如果是则更新最大和
     *   如果不是则递归遍历它的子树
     *
     * @param root
     * @return
     */
    static int maxSum = Integer.MIN_VALUE;

    public static int maxSumBST1(TreeNode root) {
        if (root == null){
            maxSum = maxSum > 0 ? maxSum : 0;
            return 0;
        }
        // 先序遍历每个节点，判断当前子树是否是BST
        State state = isValidBST(root);
        if (state.isBST) {
            maxSum = (maxSum > state.sum ? maxSum : state.sum);
        }
        maxSumBST1(root.left);// 递归判断左子树是否是BST，并更新状态
        maxSumBST1(root.right);// 递归判断右子树是否是BST，并更新状态

        return maxSum;
    }

    /**
     * 判断一棵树是否是BST
     * @param root
     * @return state
     */
    public static State isValidBST(TreeNode root) {
        State state = new State();
        isValidBST(root, state);
        return state;
    }

    /**
     * 中序遍历判断子树是否为BST
     * @param root
     * @param state
     */
    private static void isValidBST(TreeNode root, State state) {
        if (root == null) {
            state.isBST = true;
            return;
        }
        isValidBST(root.left, state); // 遍历左子树

        if (root.val <= state.preNodeVal || !state.isBST) {// 如果序列非递增or 左子树不是BST
            state.isBST = false;
            state.sum = 0;
            return;
        }

        // 当前树为BST,更新对应的状态值
        state.preNodeVal = root.val; // 更新当前的val为preNodeVal
        state.sum += root.val; // 更新键值和

        isValidBST(root.right, state); // 遍历右子树
    }

    private static class State{
        boolean isBST = false;
        long preNodeVal = Long.MIN_VALUE;
        int sum = 0;// 键值和
    }

}
